We present a simple distributed $\Delta$-approximation algorithm for maximumweight independent set (MaxIS) in the $\mathsf{CONGEST}$ model which completesin $O(\texttt{MIS}(G)\cdot \log W)$ rounds, where $\Delta$ is the maximumdegree, $\texttt{MIS}(G)$ is the number of rounds needed to compute a maximalindependent set (MIS) on $G$, and $W$ is the maximum weight of a node. %Whetherour algorithm is randomized or deterministic depends on the \texttt{MIS}algorithm used as a black-box. Plugging in the best known algorithm for MIS gives a randomized solution in$O(\log n \log W)$ rounds, where $n$ is the number of nodes. We also present a deterministic $O(\Delta +\log^* n)$-round algorithm basedon coloring. We then show how to use our MaxIS approximation algorithms to compute a$2$-approximation for maximum weight matching without incurring any additionalround penalty in the $\mathsf{CONGEST}$ model. We use a known reduction forsimulating algorithms on the line graph while incurring congestion, but we showour algorithm is part of a broad family of \emph{local aggregation algorithms}for which we describe a mechanism that allows the simulation to run in the$\mathsf{CONGEST}$ model without an additional overhead. Next, we show that for maximum weight matching, relaxing the approximationfactor to ($2+\varepsilon$) allows us to devise a distributed algorithmrequiring $O(\frac{\log \Delta}{\log\log\Delta})$ rounds for any constant$\varepsilon>0$. For the unweighted case, we can even obtain a$(1+\varepsilon)$-approximation in this number of rounds. These algorithms arethe first to achieve the provably optimal round complexity with respect todependency on $\Delta$.
展开▼
